package madixin.t1043;

class Solution {
    //动态规划
    //https://www.bilibili.com/video/av78253427
    public int maxSumAfterPartitioning(int[] A, int K) {
        if (A == null || A.length <= 0 || K < 0) {
            return 0;
        }
        int dp[] = new int[A.length];
        dp[0] = A[0];
        for (int i = 1; i < A.length; i++) {
            int max = A[i];
            for (int j = 1; j <= K && i - j + 1 >= 0; j++) {
                int pre = i - j >= 0 ? dp[i - j] : 0;
                max = Math.max(max, A[i - j + 1]);
                dp[i] = Math.max(dp[i], pre + max * j);
            }

        }
        return dp[A.length - 1];
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.maxSumAfterPartitioning(new int[]{1, 15, 7, 9, 2, 5, 10}, 3));
    }
}